Overlay networks have been suggested and are starting to be employed as a popular solution to work around rigid and often suboptimal Internet Protocol (IP) routing to provide better performance. Service overlay networking (SON) is an emerging approach for dynamic service composition that employs service nodes that provide more services than just data forwarding. For example, large networks, such as the Internet, provide the infrastructure for many peer-to-peer systems and are now being used to provide a variety of services to users, including Internet applications requiring high bandwidth such as live, high-quality, streaming video, video conferencing, and graphic-intensive multiplayer games.
Several nodes or peers in the network may be able to provide different components of the service, and these nodes and other nodes providing components for services are service nodes forming the SON. For example, for streaming video, one node provides transcoding of the content; another node may provide language translation; etc. There may be multiple nodes that are operable to provide the same components of the services. Service nodes providing different components of the streaming video service are selected and used to provide the streaming video to users.
This process of combining two or more services to provide service to a user is referred to as service composition. In an SON, each service node provides one or more basic services, referred to as component services, in addition to data forwarding. These component-services act as building blocks' for more advanced services, which can be created by combining these component-services in series or in parallel.
One of the problems in SONs is to find a service path, typically comprised of multiple service nodes providing the component services of the desired service and matching user quality of service (QoS) requirements. Overlay networks typically use measurements to infer the network state and to find the path matching QoS requirements for a given application/service. Several techniques and tools are now available to measure the network state. The problem of path selection in overlay networks, then, basically involves finding a path between a source and a destination passing through any intermediate nodes such that it will satisfy one or more QoS requirements.
Prior research proposed using an aggregate QoS constraint and finding the minimum cost path based on the aggregated constraint. The aggregation of QoS constraints, for example, derives a single value representing multiple QoS constraints. The main limitation in the proposed solutions of the prior research is that they aggregate multiple constraints using a linear function, and prior research has shown that the use of a linear function to aggregate multiple constraints might not satisfy all the QoS constraints individually. Thus, such aggregation of QoS requirements cannot guarantee that all QoS constraints are met individually, and important QoS constraints that may severely impact the service, such as delay, may not be met, resulting in poor service quality for the user.